#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>

#include <fstream>

#include "grammar.h"
#include "parser.h"
#include "item.h"
#include "forest.h"

#define VERBOSE true
#define DEBUGGING false
#define OUTPUT false

map <string, class forest *, less<string> > ForestMap;

//////////////////////////////////////////////////
//
//////////////////////////////////////////////////
void parser::print_grammar(ostream& out_stream)
{
  Grammar.print(out_stream);
}

//////////////////////////////////////////////////
//
//////////////////////////////////////////////////
void parser::print_sentence(ostream& out_stream)
{
  out_stream << "Sentence=(";
  list <pair <string, class features*> >::const_iterator SentenceIterator;
  for(SentenceIterator=Sentence.begin(); SentenceIterator != Sentence.end(); SentenceIterator++){
    if (SentenceIterator!=Sentence.begin())
      out_stream << " ";
    out_stream << "(" << (*SentenceIterator).first << ","; 
    if ((*SentenceIterator).second)
      (*SentenceIterator).second->print(out_stream);
    out_stream << ")";
  }
  out_stream << ")" << endl;
}

//////////////////////////////////////////////////
//
//////////////////////////////////////////////////
void parser::print_states(ostream& out_stream)
{
  unsigned int indx;
  for (indx = 0; indx < States.size(); indx++){
    out_stream << "Q" << indx << endl;
    ITEMSET l=*(States[indx]);
    ITEMSET::iterator pos;
    for (pos = l.begin(); pos != l.end(); ++pos) {
      (*pos)->print(out_stream);
      out_stream << endl;
    }
  }
}

//////////////////////////////////////////////////
//
//////////////////////////////////////////////////
void parser::print_last_state(ostream& out_stream)
{
  unsigned int indx;
  indx = States.size()-1;
  out_stream << endl;
  out_stream << "Q" << indx << endl;
  ITEMSET l=*States[indx];
  ITEMSET::iterator pos;
  for (pos = l.begin(); pos != l.end(); ++pos) {
    (*pos)->print(out_stream);
    out_stream << endl;
  }
  out_stream << endl;
}

//////////////////////////////////////////////////
//
//////////////////////////////////////////////////
void
parser::evaluate(string s)
{
}

//////////////////////////////////////////////////
//
//////////////////////////////////////////////////
int
parser::parse_earley()
{
  // Ajoute S' -> S
  string LastAxiom=Grammar.Initial;
  rule *LastRule=Grammar.addNewInitial("_AXIOM_");
  if (VERBOSE)
    print_grammar(cout);
  
  // Ajoute # Ã  la fin de la phrase
  Sentence.push_back(pair<string, class features*>("_END_", new class features("","","")));
  if (VERBOSE)
    print_sentence(cout);
  
  // Q0 = {[S' -> . S END, 0, (S' S)]}
  
  class item *i = new item(LastRule->getLhs(), LastRule->getRhs(), LastRule->getSem(), 0, 0);
  i->Id=LastRule->getId();
  ITEMSET *l=new ITEMSET;
  l->insert(i);
  States.push_back(l);
  if (DEBUGGING){
    cout << "#################### BEGIN ####################" << endl;
    print_last_state(cout);
  }
  list <pair <string, class features*> >::const_iterator word;
  // Iterate through list and shift each element.
  for (word=Sentence.begin(); word != Sentence.end(); word++){
    do
      ;
    while (close((*word).first) || reduce((*word).first));
    if (DEBUGGING){
      cout << "#################### CHECK POINT ####################" << endl;
      print_last_state(cout);
      cout << "#####################################################" << endl;
      //print_states(cout);
    }
    if (shift((*word).first, (*word).second)){
      
    } else { 
      cerr << "Parsing Failed" << endl;
      break;
    }
  }
  
  if (word == Sentence.end()){
    //cerr << Sentence.back().first << endl; 
    do
      ;
    while (close(Sentence.back().first) || reduce(Sentence.back().first));
    if (VERBOSE){
      print_states(cout);
      cout << endl;
    }
  }
  
  //print_states(cout);
  char s[32];
  sprintf(s, "_AXIOM_-%X-%X", 0, Sentence.size());
  map <string, class forest *, less<string> >::const_iterator ForestMapIt;
  vector <string> ForestFound;
  ForestMapIt=ForestMap.find(s);
  if (ForestMapIt!=ForestMap.end()){
    (*ForestMapIt).second->notSeen();
    (*ForestMapIt).second->eval("");
    (*ForestMapIt).second->notSeen();
    /* Affichage du graphe */

    //    cout << "digraph D {" << endl;
    //    (*ForestMapIt).second->print(cout);
    //    cout << "}" << endl;vector<string> Rhs
    
    /* Crée le graphe */
    ofstream out_file("analyse.dot", ios::trunc);
    out_file << "digraph D {" << endl;
    (*ForestMapIt).second->print(out_file);
    out_file << "}" << endl;
    out_file.close();

    return 0;
  }
}

//////////////////////////////////////////////////
//
//////////////////////////////////////////////////
bool
parser::shift(string word, class features *sem)
{
   //cerr << "###SHIFT###" << __FILE__ << "(" << __LINE__ << ")" << word.first;
  bool modification=false;
  unsigned int i=States.size()-1;
  ITEMSET::const_iterator iterItem;
  ITEMSET *l = new ITEMSET;
  //cout << "\t\t\t\tshift:" << s << endl;
  for (iterItem=States[i]->begin(); iterItem != States[i]->end(); iterItem++){
    if ((*iterItem)->Rhs.size()>(*iterItem)->Index){
      string suivant=(*iterItem)->Rhs[(*iterItem)->Index];
      // A -> x . ai y
      if (suivant==word){
	item *it = new item((*iterItem)->Lhs, (*iterItem)->Rhs, (*iterItem)->Sem, (*iterItem)->Index+1, (*iterItem)->Rang);
	it->Id=(*iterItem)->Id;
	char s[32];
	sprintf(s, "%s-%X-%X", word.c_str(), i, i+1);
	
	it->SonsSpan=(*iterItem)->SonsSpan;
	it->SonsSpan.push_back(s);
	if (it->SonsSpanStr.size())
	  it->SonsSpanStr += ".";
	it->SonsSpanStr += s;
	pair<ITEMSET::iterator, bool> result = l->insert(it);
	ForestMap[s]=new forest(word, sem);
	ForestMap[s]->addNode(word);
      	modification=true;
      }
    }
  }
  States.push_back(l);
  if (DEBUGGING){
    cout << "#################### SHIFT (" << word << ") ####################" << endl;
    print_last_state(cout);
  }
  return modification;
}

//////////////////////////////////////////////////
//
//////////////////////////////////////////////////
bool
parser::close(string word)
{
  //cerr << "###CLOSE###" << __FILE__ << "(" << __LINE__ << ")" << word << endl;
  //if (word.second)
  //  word.second->print(cerr, true);
  //cerr << endl;
  bool modification=false;
  unsigned int i=States.size()-1;
  // Iterate through list
  for (ITEMSET::const_iterator iterItem=States[i]->begin(); iterItem != States[i]->end(); iterItem++){
    //(*iterItem)->print(cerr); cerr << endl;
    // X -> a . A b
    if ((*iterItem)->Rhs.size() > (*iterItem)->Index){
      //cout << __LINE__ << endl;
      string suivant=(*iterItem)->Rhs[(*iterItem)->Index];
      set<string>::const_iterator iter;
      // Iterate through list
      for (iter=Grammar.NonTerminals.begin(); iter != Grammar.NonTerminals.end(); iter++){
	if ((*iter)==suivant)
	  // Iterate through list
	  for (RULESET::const_iterator iterRules=Grammar.Rules.begin(); iterRules != Grammar.Rules.end(); iterRules++){
	    vector<string> Rhs = (*iterRules)->Rhs;
	    if ((suivant==(*iterRules)->Lhs)) {
	      
	      // A(...)
	      item *it = new item((*iterRules)->Lhs, (*iterRules)->Rhs, (*iterRules)->Sem, 0, i);
	      it->Id=(*iterRules)->Id;
	      // insertion ensembliste
	      pair<ITEMSET::iterator, bool> result = States[i]->insert(it);
	      if (DEBUGGING){
	      	if (!result.second){
		  cout << "#################### CLOSE (" << suivant << ", " << word << ") WITHOUT EFFECT ####################" << endl;
		} else {
		  cout << "#################### CLOSE (" << suivant << ", " << word << ")####################" << endl;
		}
	      }
	      modification=modification || result.second;
	    }
	  }
      }
    }
  }
  return modification;
}

//////////////////////////////////////////////////
//
//////////////////////////////////////////////////
bool
parser::reduce(string word)
{
  //cerr << "###REDUCE###" << __FILE__ << "(" << __LINE__ << ")" << word.first.second;
  //if (word.second)
  //  word.second->print(cerr, true);
  //cerr << endl;
  bool modification=false;
  unsigned int i=States.size()-1;
  ITEMSET::const_iterator iterItem;
  // Iterate through list
  for (iterItem=States[i]->begin(); iterItem != States[i]->end(); iterItem++){
    // iterItem: A -> a ., k
    if ((*iterItem)->finished()){
      //cout << "ItemYEP:" ; (*iterItem)->print(cout); cout << endl;
      if (!(*iterItem)->Seen){
	char s[32];
	sprintf(s, "%s-%X-%X", (*iterItem)->Lhs.c_str(), (*iterItem)->Rang, i);
	// A_x_y
	
	// On ajoute A_x_y à la table des forêts
	class forest *ForestFound;
	map <string, class forest *, less<string> >::const_iterator ForestMapIt=ForestMap.find(s);
	if (ForestMapIt!=ForestMap.end())
	  ForestFound=(*ForestMapIt).second;
	else {
	  ForestMap[s]=new forest((*iterItem)->Lhs, (*iterItem)->Sem);
	  ForestFound=ForestMap[s];
	}
	
	//cerr << s << " -> " << endl;
	node *n = new node(s);
	// On construit les noeuds de la forêt
	for(vector<string>::const_iterator son=(*iterItem)->SonsSpan.begin() ; son!=(*iterItem)->SonsSpan.end() ; son++){
	  //cerr << " PUSH " << *son << ":" << ForestMap.find(*son)->second << endl;
	  n->Sons.push_back(ForestMap.find(*son)->second);
	}
	ForestFound->Nodes.push_back(n);
	
	(*iterItem)->Seen=true;
	(*iterItem)->Span=s;
	
	if (OUTPUT){
	  cout << s << " -> ";
	  bool first=true;
	  for(vector<string>::const_iterator it=(*iterItem)->SonsSpan.begin() ; it!=(*iterItem)->SonsSpan.end() ; it++){
	    if (first)
	      first=false;
	    else
	      cout << " ";
	    cout << *it;
	  }
	  cout << endl;
	}
      }
      
      // Iterate through list
      // Qk 
      for (ITEMSET::const_iterator iterItem2=States[(*iterItem)->Rang]->begin(); iterItem2 != States[(*iterItem)->Rang]->end(); iterItem2++){
	// iterItem2: X -> b . A c
	if (((*iterItem2)->Rhs.size() > (*iterItem2)->Index) &&
	    (*iterItem2)->Rhs[(*iterItem2)->Index] == (*iterItem)->Lhs){
	  // it: X -> b A . c
	  item *it = new item((*iterItem2)->Lhs, (*iterItem2)->Rhs, (*iterItem2)->Sem, (*iterItem2)->Index+1, (*iterItem2)->Rang);
	  it->Id=(*iterItem2)->Id;
	  if ((*iterItem2)->SonsSpan.size()){
	    for(vector<string>::const_iterator it2=(*iterItem2)->SonsSpan.begin() ; it2!=(*iterItem2)->SonsSpan.end() ; it2++){
	      it->SonsSpan.push_back(*it2);
	      if (it->SonsSpanStr.size())
		it->SonsSpanStr += ".";
	      it->SonsSpanStr += (*it2);
	    }
	  }
	  it->SonsSpan.push_back((*iterItem)->Span);
	  if (it->SonsSpanStr.size())
	    it->SonsSpanStr += ".";
	  it->SonsSpanStr += (*iterItem)->Span;
	  
	  // on insert un nouvel item
	  pair<ITEMSET::iterator, bool> result = States[i]->insert(it);
	  
	  if (DEBUGGING){
	    if (!result.second){
	      ITEMSET::iterator FindItem = result.first;
	      cout << "#################### REDUCE AGAIN (" << word << ")####################" << endl;
	    }
	    else{
	      cout << "#################### REDUCE (" << word << ")####################" << endl;
	      print_last_state(cout);
	    }
	  }
	  modification=modification || result.second;
	}
      }
    }
  }
  return modification;
}
